import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串 
     * @return bool布尔型
     */

    //判断左右括号符号是否匹配
    private static boolean isMatch(char left,char right){

        if(left==')'){
            return right=='(';
        }else if(left==']'){
            return right=='[';
        }else{
            return right=='{';
        }

    }
    public boolean isValid (String s) {

        Stack<Character> stack=new Stack<>();

        for( int i=0 ;i<s.length(); i++){
            //如果是左括号直接入栈
            if(s.charAt(i)=='('||s.charAt(i)=='['||s.charAt(i)=='{'){
                stack.push(s.charAt(i));

            }else{
                //否则是右括号
                if(stack.isEmpty()){
                    //如果是右括号且栈里没存有左括号，则不是有效括号序列
                    return false;
                }else{
                    //已经判断了左右是否匹配，需要判断符号是否匹配，防止（】，（}，【}等情况
                    char right=stack.peek();
                    //查看栈顶元素，判断左右符号是否匹配，不匹配返回false
                    //匹配则出栈，进行下一次循环判断
                    if(isMatch(s.charAt(i),right)){
                        stack.pop();
                    }
                }
            }
        }
        //如果最后遍历完了以后栈里还有元素没有匹配成功出栈，说明不是有效括号序列
        if(!stack.isEmpty()){
            return false;
        }
        return true;
    }
}